package com.yb.chapter1;

import java.util.Stack;

/**
 * 描述：设计一个有getMin功能的栈
 * 要求：设计一个满足基本功能的栈，在此基础上再实现返回当前栈中最小元素的操作
 *       push pop getMin 的时间复杂度都是O(1)
 *       设计的栈可以使用现有的栈
 *
 *  思路：O(1)的时间复杂度，肯定是需要空间来换的，所以在维护栈的情况下，
 *  需要维护一个当前栈的最小值的数据结构
 *
 * @author yb
 * @date 2021/12/24 15:02
 */
public class GetMinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public GetMinStack(){
        dataStack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public Integer push(Integer data){
        if(minStack.isEmpty()){
            minStack.push(data);
        }else if(data < getMin()){
            minStack.push(data);
        }else{
            //拿出最小的再放一份
            minStack.push(minStack.peek());
        }

        return dataStack.push(data);
    }

    public Integer pop(){
        if(minStack.isEmpty()||dataStack.isEmpty()){
            throw new NullPointerException("栈空");
        }
        minStack.pop();
        return dataStack.pop();
    }

    public Integer getMin(){
        if(minStack.isEmpty()){
            throw new NullPointerException("栈空");
        }
        return minStack.peek();
    }


    public static void main(String[] args) {
        GetMinStack stack = new GetMinStack();
        stack.push(4);
        System.out.println(stack.getMin());
        stack.push(3);
        System.out.println(stack.getMin());
        stack.push(2);
        System.out.println(stack.getMin());
        stack.push(5);
        System.out.println(stack.getMin());
        stack.push(-1);
        System.out.println(stack.getMin());

        System.out.println("==================");
        System.out.println("出栈==》"+stack.pop());
        System.out.println("最小值==》"+stack.getMin());
        System.out.println("出栈==》"+stack.pop());
        System.out.println("最小值==》"+stack.getMin());
        System.out.println("出栈==》"+stack.pop());
        System.out.println("最小值==》"+stack.getMin());
        System.out.println("出栈==》"+stack.pop());
        System.out.println("最小值==》"+stack.getMin());
        System.out.println("出栈==》"+stack.pop());
        System.out.println("最小值==》"+stack.getMin());
    }

}
